#include "../8.3.1.Adjacency matrix/ljjz.c"

// 定义布尔类型
typedef enum
{
    FALSE,
    TRUE
} boolean;
// 距离向量类型
typedef int dist[M];
// 路劲类型
typedef int path[M];

/**
 * Dijkstra算法求单源最短路径
 * @param {Mgraph}          g               图的邻接矩阵存储结构
 * @param {int}             v               源点
 * @param {dist}            p               路径向量
 * @param {path}            d               距离向量
 * @return void
 */
void dijkstra(Mgraph g, int v, path p, dist d)
{
    // 表示当前元素是否已经确定最短路径
    boolean final[M];
    int i, j, k, min, x;

    // 第1步 初始化集合 S 与距离向量 d
    for (i = 0; i < g.n; i++)
    {
        final[i] = FALSE;
        d[i] = g.edges[v][i];

        if (d[i] < FINITY && d[i] != 0)
        {
            p[i] = v;
        }
        else
        {
            p[i] = -1;
        }
    }

    final[v] = TRUE;
    d[v] = 0;

    // 第2步 依次找出 n - 1 个结点加入到 S 中
    for (i = 1; i < g.n; i++)
    {
        min = FINITY;
        for (k = 0; k < g.n; ++k)
            if (!final[k] && d[k] < min)
            {
                v = k;
                min = d[k];
            }
        printf("\n %c -------- %d \n", g.vexs[v], min);

        if (min == FINITY)
        {
            return;
        }

        final[v] = TRUE;
    }

    // 第3步 修改 S 与 V-S 中顶点的距离
    for (i = 0; i < g.n; i++)
    {
        if (!final[i] && (min + g.edges[v][i] < d[i]))
        {
           d[i] = min + g.edges[v][i];
            p[i] = v;
        }
    }
}


/**
 * 输出有向图的最短路径
 * @param {Mgraph}          g               图的邻接矩阵存储结构
 * @param {path}            p               路径向量
 * @param {dist}            d               距离向量
 * @return void
 */
void print(Mgraph g, path p, dist d)
{
    int st[M], i , pre, top = -1;

    for(i = 0; i < g.n; i++) {
        printf("\n Distancd: %7d",d[i]);
        st[++top] = i;

        while (pre != -1)
        {
            st[++top] = pre;
            pre = p[pre];
        }

        while (top > 0)
        {
           printf("%2d", st[top--]);
        }
    
    }
}

int main() {
    Mgraph g;
    path p;
    dist d;
    int v0;
    creat(&g, "g13.txt",1);
    printf("please input the source vertex: ");
    scanf("%d", &v0);
    dijkstra(g, v0, p, d);
    print(g, p, d);
    return 0;
}